paste_iknn199c

注意:本页面是由自动化程序生成的剪贴板存档。

#include <cstdio>
#define N 1000001
int rk[3*N+100], sa[3*N], bu[N], x[N], y[N];
void sort(int *rk, int *a, int *b, int n, int m) {
	for (int i = 0; i <= m; i++) bu[i] = 0;
	for (int i = 0; i < n; i++) bu[rk[a[i]]]++;
	for (int i = 1; i <= m; i++) bu[i] += bu[i-1];
	for (int i = n-1; i >= 0; i--) b[--bu[rk[a[i]]]] = a[i];
}
bool cmp3(int *r, int x, int y) {
	return r[x] == r[y] && r[x+1] == r[y+1] && r[x+2] == r[y+2];
}
bool cmpt(int* r, int x, int y) {
	if (r[x] != r[y]) return r[x] < r[y];
	if (x%3 == 1) return bu[x+1] < bu[y+1];
	else return !cmpt(r, y+1, x+1);
}
void DC3(int *rk, int *sa, int n, int m) {
	bool h = (n%3 == 1); if (h) rk[n++] = 0;
	int *rn = rk+n+2, *san = sa+n, ln = 0, p;
	for (int i = 0; i < n; i++)
		if (i % 3) x[ln++] = i;
	rk[n] = rk[n+1] = 0;
	sort(rk+2, x, y, ln, m);
	sort(rk+1, y, x, ln, m);
	sort(rk, x, y, ln, m);
	int ta = 0, td = (n+1)/3;
	#define F(x) (x/3)+(x%3==1?0:td)
	rn[F(y[0])] = p = 1;
	for (int i = 1; i < ln; i++) {
		if (!cmp3(rk, y[i], y[i-1])) p++;
		rn[F(y[i])] = p;
	}
	if (p < ln) DC3(rn, san, ln, p);
	else for (int i = 0; i < ln; i++)
		if (rn[i]) san[rn[i]-1] = i;
	for (int i = 0; i < ln; i++)
		if (san[i] < td) y[ta++] = san[i]*3;
	sort(rk, y, x, ta, m);
	#define G(x) (x>=td?(x-td)*3+2:x*3+1)
	for (int i = 0; i < ln; i++)
		bu[y[i] = G(san[i])] = i;
	bu[n] = -1;
	int i = 0, j = h; p = 0;
	while (i < ta && j < ln) {
		if (cmpt(rk, y[j], x[i])) sa[p++] = y[j++];
		else sa[p++] = x[i++];
	}
	while (i < ta) sa[p++] = x[i++];
	while (j < ln) sa[p++] = y[j++];
}
char s[N]; int n;
int main() {
	scanf("%s", s);
	for (n = 0; s[n]; n++)
		rk[n] = s[n]-'0'+1;
	DC3(rk, sa, n, 75);
	for (int i = 0; i < n; i++)
		printf("%d ", sa[i]+1);
	puts("");
}